#对数组进行全排列
#DFS 递归进行
#DFS BFS是人类思考问题的基本思维方式

from typing import List
class Solution:
    #给定一个 没有重复 数字的序列，返回其所有可能的全排列。
    def permute(self, nums: List[int]) -> List[List[int]]:

        all_res = []
        res = [0] * len(nums)
        book = [0] * len(nums)

        #进行DFS递归的函数
        def helper(index):
            #终止条件
            if index == len(nums):
                all_res.append(res[:])#注意 这里要传入副本 如果直接传入res 那么对res的修改就是对所有结果的修改
                return

            #进入下一种情况
            for i, b in enumerate(book):
                #一些条件（具体情况的，减枝）
                if b == 0:
                    res[index] = nums[i]
                    book[i] = 1
                    helper(index + 1)
                    #回溯 情况的回退
                    book[i] = 0

        helper(0)
        return all_res

    #给定一个可包含重复数字的序列，返回所有不重复的全排列
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        all_res = []
        res = [0] * len(nums)
        used = [False] * len(nums)

        def helper(index):
            if index == len(nums):
                all_res.append(res[:])
                return

            for i, usd in enumerate(used):
                if usd == False:
                    #进行减枝
                    if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False:
                        continue
                    res[index] = nums[i]
                    used[i] = True
                    helper(index + 1)
                    used[i] = False

        nums.sort()
        helper(0)
        return all_res

    '''
    给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

    candidates 中的每个数字在每个组合中只能使用一次。
    输入: candidates = [10,1,2,7,6,1,5], target = 8,
    所求解集为:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]
    '''
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates = sorted(candidates)
        num = len(candidates)
        res = []
        if num == 0:
            return res

        comb = [0]
        used = [False] * num

        # print(candidates)
        def permutation(index):
            # print(comb[1:])
            if sum(comb) > target:
                return
            elif sum(comb) == target:
                res.append(comb[1:])
                return

            for i, cand in enumerate(candidates):
                # i>index的目的是让组合都保持递增顺序 就不会有一个组合重复排序出现了 比如(1,2,3), (2,1,3),(3,2,1)
                # 用递增保证一个组合就一个唯一表示
                if used[i] == False and i >= index:

                    # 减枝：出发点和前一个一样，并且不是前一个一起参与组成的情况
                    # 例如：题目中 第一个1和其他数组合后（包括1和1同时参与组合） 第二个1和其他数组合就重复了
                    if i > 0 and candidates[i] == candidates[i - 1] and used[i - 1] == False:
                        continue

                    used[i] = True
                    comb.append(cand)
                    permutation(i)
                    comb.pop()
                    used[i] = False

        permutation(0)
        return res

L = [1,2,3]
solution = Solution()
print(solution.permute(L))
